算法分析的两个主要方面是时间复杂度和空间复杂度的分析。
和具有相同的增长速度。
斐波那契数列的定义为：, , , =2, 3, …。用递归函数计算的空间复杂度是。
要从50个键值中找出最大的3个值，选择排序比堆排序快。
对于顺序存储的长度为的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为和。
若用链表来表示一个线性表，则表中元素的地址一定是连续的。
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
队列的特性
队列是后进先出的线性表。
对于二项式队列，归并操作的平均时间复杂度是常数级。
某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。
若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。
将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。
在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。
任何AVL树的中序遍历结果是有序的（从小到大）。
对AVL树中的任一结点，其右子树的高度一定比其左子树的高度要高。
如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3（根结点的深度是1），则结点2或者结点3一定有两个子结点。
在有个元素的最大堆中，随机访问任意键值的操作可以在时间完成。
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。
用一维数组G[]存储有4个顶点的无向图如下：
G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
无向连通图至少有一个顶点的度为1。
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。
Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。
P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。
在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。
如果从有向图 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。
采用递归方式对顺序表进行快速排序，每次划分后，先处理较短的分区可以减少递归次数。
对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。
在散列中，函数“插入”和“查找”具有同样的时间复杂度。
将 10 个元素散列到 100 000 个单元的哈希表中，一定不会产生冲突。
假设模式串是abababaab，则KMP模式匹配算法中的next[j] = 0 1 1 2 3 4 5 6 2。
下列排序算法的常规实现中，除去对原始数据的保存以外，哪些算法的额外空间复杂度是O(1)？
关于顺序查找算法
顺序查找算法能适用于 ▁▁▁▁▁ 。
非空线性表的结构特征
非空线性表具有哪些结构特征？
用后序和中序构造二叉树时，根据后序找出根结点，根据中序分左右子树。
如果后序序列存储在数组a中，下标从i~j为当前子树存储的元素。
如果中序序列存储在数组b中，下标从s~t为当前子树存储的元素。
那么构造二叉树时，此子树的根结点是
根据此结点，可在数组b中找到对应的元素，假定下标为k。
则根据中序序列的特性，可知，
此二叉树的左子树在数组b中的下标的起点为s，终点为
右子树在数组b中的下标的起点为
那么，其左子树对应在数组a中的下标起点为i，终点为i+
右子树对应在数组a中的下标起点为
注意：填空时均不要加空格
给定一组整数：
{ 36, 25, 81, 17, 49 }
采用直接插入排序法按升序排序，请写出经过一趟排序后的结果：
{ 1分, 1分, 1分, 1分, 1分 }
给定一组整数：
{ 36, 25, 81, 17, 49 }
采用快速排序法按升序排序，请写出将首个元素作为枢轴（支点）经过一趟排序后的结果：
{ 1分, 1分, 1分, 1分, 1分 }
下列代码的功能是将存有N个元素的数组A[]调整为最大堆。
#define leftchild(i) ( 2*(i)+1 )
void BuildMaxHeap( ElementType A[], int N )
{ int i, j, child;
ElementType Tmp;
for ( i = (N-1)/2; i >= 0; i-- ) {
j = i;
for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
child = leftchild(j);
if (3分)
child ++;
if (3分) A[j] = A[child];
else break;
}
3分;
}
}
感谢燕山大学窦燕老师修正题目！
下列代码的功能是将小顶堆H中指定位置P上的元素的整数键值下调D个单位，然后继续将H调整为小顶堆。
void DecreaseKey( int P, int D, PriorityQueue H )
{
int i, key;
key = H->Elements[P] - D;
for ( i = 3分; H->Elements[i/2] > key; i/=2 )
3分;
H->Elements[i] = key;
}